package site.wanjiahao;

public class Main {

    public static void main(String[] args) {
        System.out.println(fib2(3));
        System.out.println(fib1(3));
    }

    // 斐波那契
    // 递归形式 0 1 1 2 3
    // 时间复杂度为 O(2^n)
    public static int fib1(int n) {
        // 0 1返回数值
        if (n <= 1) return n;
        return fib1(n -1) + fib1(n - 2);
    }

    // 非递归形式
    // 时间复杂度为 O(n)
    public static int fib2(int n) {
        if (n <= 1) return n;

        int first = 0;
        int second = 1;
        while(n-- > 1) {
            second = first + second;
            first = second - first;
        }
        return second;
    }

}
